package leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

public class Solution17 {

    public static void main(String[] args) {
        String digits = "27";
        System.out.println(new Solution17().letterCombinations(digits));
    }

    public List<String> letterCombinations(String digits) {
        if(digits.length()==0) return new ArrayList<String>();
                //‘a’ ascii 97
        ArrayList<char[]> numToChar = new ArrayList<>();
        for (int i = 2; i <= 9; i++) {
            int start;
            char[] chars = null;
            if(i<=7) start = (i-2)*3+97;
            else start = (i-2)*3+97+1;
            if(i==7||i==9) chars = new char[]{(char)start,(char)(start+1),(char)(start+2),(char)(start+3)};
            else chars = new char[]{(char)start,(char)(start+1),(char)(start+2)};
            numToChar.add(chars);
        }
        ArrayList<String> total = new ArrayList<>();
        backTrace(total,numToChar,digits,new StringBuilder());
        return total;
    }

    public void backTrace(ArrayList<String> total,ArrayList<char[]> numToChar,String digits,StringBuilder sb){
        if(sb.length()==digits.length()){
            total.add(sb.toString());
            return;
        }
        int curDigit = digits.charAt(sb.length())-'2';
        char[] curPossiableChars = numToChar.get(curDigit);
        for (int i = 0; i < curPossiableChars.length; i++) {
            sb.append(curPossiableChars[i]);
            backTrace(total,numToChar,digits,sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}
